package mine.code.question.动态规划;

import org.junit.Test;

import java.util.HashSet;
import java.util.Set;

/**
 * 一条包含字母A-Z 的消息通过以下映射进行了 编码 ：
 * <p>
 * 'A' -> 1
 * 'B' -> 2
 * ...
 * 'Z' -> 26
 * 要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：
 * <p>
 * "AAJF" ，将消息分组为 (1 1 10 6)
 * "KJF" ，将消息分组为 (11 10 6)
 * 注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。
 * <p>
 * 给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
 * <p>
 * 题目数据保证答案肯定是一个 32 位 的整数。
 *
 * @author caijinnan
 */
public class 解码方法 {

    @Test
    public void run() {
        String s = "1121";
        System.out.println(numDecodings(s));
    }

    Set<String> set = new HashSet<>();

    {
        for (int i = 10; i <= 26; i++) {
            set.add(String.valueOf(i));
        }
    }

    public int numDecodings(String s) {
        if (s.startsWith("0") || s.length() == 0) {
            return 0;
        }
        char[] chars = s.toCharArray();
        int length = chars.length;
        // dp[i] = s.charAt(i) == 0
        int[] dp = new int[length];
        dp[0] = 1;
        for (int i = 1; i < length; i++) {
            String o = "" + chars[i - 1] + chars[i];
            if (chars[i] == '0') {
                int num = 0;
                if (set.contains(o)) {
                    if (i != 1) {
                        num = dp[i - 2];
                    } else {
                        num = 1;
                    }
                }
                dp[i] = num;
                continue;
            }
            if (set.contains(o)) {
                int addNum;
                if (i != 1) {
                    addNum = dp[i - 2];
                }else{
                    addNum = 1;
                }
                dp[i] = dp[i - 1] + addNum;
            } else {
                dp[i] = dp[i - 1];
            }
        }
        return dp[length - 1];
    }

}
